package com.javabasic.algorithm.leetcode;

/**
 * 解题算法：O(N)
 * 链接： https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/hua-jie-suan-fa-19-shan-chu-lian-biao-de-dao-shu-d/
 */
public class RemoveNthNodeFromEndofList {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        int len = 0;
        ListNode now = head, pre;
        while (now != null) {
            now = now.next;
            len++;
        }
        if (len > n) {
            int tag = len - n;
            now = head;
            pre = head;
            while (now != null && tag > 0) {
                pre = now;
                now = now.next;
                tag--;
            }
            if (tag == 0) {
                pre.next = now.next;
            }
        } else if (len == n) {
            head = head.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 */
//class ListNode {
//    int val;
//    ListNode next;
//    ListNode(int x) { val = x; }
//}
